package main

/*
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
*/
func main() {
	println(isValid("(([]){})"))

}

/**
 *	isValid
 *	@Description: 栈 先进后出
 *	@param s string
 *	@return bool
 */
func isValid(s string) bool {
	n := len(s)
	m := map[byte]int{}
	m['('] = 1
	m[')'] = 2
	m['['] = 3
	m[']'] = 4
	m['{'] = 5
	m['}'] = 6
	top := -1
	stack := map[int]byte{}
	for i := 0; i < n; i++ {
		if m[s[i]]%2 == 1 {
			top++
			stack[top] = s[i]
		} else if m[s[i]]%2 == 0 {
			if top == -1 {
				return false
			}
			if m[s[i]]-m[stack[top]] != 1 {
				return false
			}
			top--
		}
	}
	if top == -1 {
		return true
	}
	return false
}
